package cn.com.mdx.sort.practice;

import cn.com.mdx.sort.SortUtils;

/**
 * <p> 排序练习
 *
 * @author ：huangy
 * @date ：Created in 2020/9/15 9:50 上午
 */
@SuppressWarnings(value = {"rawtypes"})
public class SortPractice {

    private static int count = 0;

    /**
     * <p> 数组合并问题
     * 问题描述：
     * 假设
     * 1.子数组a[0]~a[n-1]已排序
     * 2.子数组a[n]~a[2n-1]已排序
     * <p>
     * 请问如何通过长度为n的辅助数组(代替长度为2n的辅助数组)
     * 来合并两数组使它继续有序?
     *
     * @param array 要合并的数组
     * @return void
     * @Author huangy
     * @description //TODO 通过长度为n的辅助数组合并长度为2n的数组
     * @date 9:53 上午 2020/9/15
     **/
    public static void mergeArray(Comparable[] array) {
        //判断数组是否合法
        if (array == null || array.length <= 1) return;
        int N = array.length;
        int mid = N / 2;
        //通过长度为原数组一半的辅助数组
        Comparable[] auxArray = new Comparable[mid];
        //将数组的0~n-1拷贝到辅助数组中
        System.arraycopy(array, 0, auxArray, 0, auxArray.length);
        //合并数组
        int i = 0;
        int j = mid;
        for (int k = 0; k < N; k++) {
            if (i > auxArray.length - 1) array[k] = array[j++];
            else if (j > N - 1) array[k] = auxArray[i++];
            else if (SortUtils.great(auxArray[i], array[j])) array[k] = array[j++];
            else array[k] = auxArray[i++];
        }
    }

    /**
     * <p> 线性时间计算数组逆序对
     * 何为逆序对，在数组中 if i < j and a[i] > a[j]
     * 则可以说数组中a[i]和a[j]两个元素就是逆序对
     * 在归并排序的基础上进行数量的叠加
     *
     * @param array 要计算的数组
     * @param temp  临时数组
     * @param low   起始位置
     * @param high  结束位置
     * @Author huangy
     * @description //TODO
     * @date 5:12 下午 2020/9/15
     **/
    public static void countInversions(Comparable[] array, Comparable[] temp, int low, int high) {
        if (high <= low) return;
        int mid = (low + high) >>> 1;
        countInversions(array, temp, low, mid);
        countInversions(array, temp, mid + 1, high);
        if (SortUtils.less(array[mid], array[mid + 1])) return;
        merge(array, temp, low, high);
    }

    private static void merge(Comparable[] array, Comparable[] temp, int low, int high) {
        int mid = (low + high) >>> 1;
        if (high + 1 - low >= 0) System.arraycopy(array, low, temp, low, high + 1 - low);
        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            if (i > mid) array[k] = temp[j++];
            else if (j > high) array[k] = temp[i++];
            else if (SortUtils.great(temp[i], temp[j])) {
                array[k] = temp[j++];
                //如果后面的数小于前面的数，则可以推测逆序对的个数为i到mid的个数
                count += mid - i + 1;
            } else array[k] = temp[i++];
        }
    }

    /**
     * <p> 暴力方式计算数组的逆序对
     * 通过两层循环逐个判断数组的逆序对
     * ,1,2,0,5,3,9,8,4,
     * 1 : 1-0
     * 2 : 2-0
     * 0 : 0
     * 5 : 5-3 5-4
     * 3 : 0
     * 9 : 9-8 9-4
     * 8 : 8-4
     * 4 : 0
     *
     * @param array 要计算的数组
     * @return int
     * @Author huangy
     * @description //TODO 计算给定数组的逆序对个数-暴力
     * @date 3:14 下午 2020/9/15
     **/
    public static int countInversionsForce(Comparable[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++)
            for (int j = i + 1; j < array.length; j++)
                if (SortUtils.great(array[i], array[j])) count++;
        return count;
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[]{1, 5, 5, 7, 8, 10, 15, 20, 0, 6, 8, 9, 10, 11, 23, 31};
        array = new Integer[]{1, 2, 0, 5, 3, 9, 8, 4};
        testCountInversions(array);
        //testCountInversionsForce(array);
        //testMergeArray(array);
    }

    /**
     * 测试合并数组
     *
     * @param array 要合并的数组
     */
    public static void testMergeArray(Comparable[] array) {
        SortUtils.printArray(array);
        mergeArray(array);
        SortUtils.printArray(array);
    }

    /**
     * 逆序对算法测试
     *
     * @param array 要计算的数组
     */
    public static void testCountInversions(Comparable[] array) {
        SortUtils.printArray(array);
        countInversions(array, new Comparable[array.length], 0, array.length - 1);
        System.out.println("上述数组的逆序对数量是：" + count);
        SortUtils.printArray(array);
    }

    /**
     * 逆序对(暴力)算法测试
     *
     * @param array 要计算的数组
     */
    public static void testCountInversionsForce(Comparable[] array) {
        SortUtils.printArray(array);
        System.out.println("上述数组的逆序对数量是：" + countInversionsForce(array));
    }


}
